/*
Problem Description
Give a number n, find the minimum x(x>0) that satisfies 2^x mod n = 1.
Input
One positive integer on each line, the value of n.
Output
If the minimum x exists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replace x and n with specific numbers.
Sample Input
2
5
Sample Output
2^? mod 2 = 1
2^4 mod 5 = 1
 */
package com.yuan.algorithms.practice201512;

import java.util.Scanner;

/**
 * @author YouYuan <br>
 *         E-mail:1265161633@qq.com <br>
 *         创建时间：2015年12月12日 上午10:25:14 <br>
 *         说明:欧拉定理a^phi(n)≡1(mod n),phi(n)=与n互素的数的个数。欧拉函数得出的解不一定是最小解，不过必定是最小解的倍数。
 */
public class 求2的x次方模n等于1 {

	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		while (in.hasNext()) {
			int n = in.nextInt();
			if ((n & 1) == 0 || n == 1) {// n为偶数或n=1无解
				System.out.println("2^? mod " + n + " = 1");
				continue;
			}
			/*
			// 解法一：暴力搜索。此方法最快。
			int x = 1;
			int mod = 2;
			while (mod != 1) {
				mod *= 2;
				mod %= n;// 取余，同时减小数据规模
				x++;
			}
			System.out.println("2^" + x + " mod " + n + " = 1");
			*/
			// 解法二：欧拉定理a^phi(n)≡1(mod n),phi(n)=与n互素的数的个数。较慢，待优化。答案错误，未知。
			int eulerX = phi(n);// 欧拉函数得出的解不一定是最小解，不过必定是最小解的倍数
			// 从欧拉函数开始向下寻找最小的解
			int minX = eulerX;
			int sqrtX = eulerX/2;
			for (int i = sqrtX; i > 1; i--) {
				if (eulerX % i == 0) {
					int temp = eulerX / i;
//					if (isX(temp, n)) {
					if (montgomery(2, temp, n) == 1) {
						minX = temp;
						break;
					}
				}
			}
			System.out.println("2^" + minX + " mod " + n + " = 1");
/*
			//解法三：蒙哥马利幂模运算 - 蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法
			for (int i = 1; i > 0; i++) {
				if (montgomery(2, i, n) == 1) {
					System.out.println("2^" + i + " mod " + n + " = 1");
					break;
				}
			}
			*/
		}
	}

	/**
	 * 快速求解a^b%k
	 * @param a
	 * @param b
	 * @param k
	 * @return
	 */
	private static long montgomery(long a, int b, int k) {
		long ans = 1;
		while(b != 0) {
			if ((b&1)==1) {
				ans = (ans*a)%k;
			}
			b >>= 1;
			a = (a*a)%k;
		}
		return ans;
	}

	/**
	 * 求欧拉函数
	 * @param n
	 * @return
	 */
	private static int phi(int n) {
		if (isPrime(n)) {
			return n - 1;//质数n的欧拉函数为n-1
		}
		int sum = 0;
		for (int i = 1; i < n; i++) {
			if (gcd(n, i) == 1) {
				sum++;
			}
		}
		return sum;
	}

	private static boolean isPrime(int n) {
		if (n < 2) {
			return false;
		}
		if ((n & 1) == 0) {
			return n == 2;
		}
		double sqrtN = Math.sqrt(n);
		for (int i = 3; i <= sqrtN; i += 2) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 求最小公因数
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int gcd(int a, int b) {
		return a == 0 ? b : gcd(b % a, a);
	}

}
